package com.mgq.algorithm.dp;

/**
 * 给定array[] 表示面值数,给定一个数字m, 用数组的数据凑够m有多少种方式,每种面值都可以用多次
 */
public class CoinsWays {
    public static void main(String[] args) {
        int i = way1(new int[]{3, 2, 5, 10}, 10);
        int j = dp2(new int[]{3, 2, 5, 10}, 10);
        System.out.println(i==j);
    }

    public static int way1(int[] array, int M) {
       return process(array, 0, M);
    }
    /**
     *
     * @param array
     * @param index 当前位置
     * @param rest
     * @return
     */
    public static int process(int[] array, int index, int rest) {
        if (index == array.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways=0;
        //array[index] 0张,1张.....不要超过rest
        for (int zhang = 0; array[index] * zhang <= rest; zhang++) {
            ways += process(array, index + 1, rest - array[index] * zhang);
        }
        return ways;
    }

    /**
     * dp版本, 未进行优化
     * @param array
     * @param index
     * @param rest
     * @return
     */
    public static int dp(int[] array, int index, int rest) {
        int N = array.length + 1;
        int[][] dp = new int[N][rest + 1];
        dp[N][0]=1;
        //从下往上, 上面的依赖下面的
        for (int i = N; i >=0; i--) {
            for (int j = 0; j <= rest; j++) {
                for (int zhang = 0; array[index] * zhang <= rest; zhang++) {
                    dp[i][j] += dp[index + 1] [rest - array[index] * zhang];
                }
            }
        }
        return dp[0][rest];
    }

    /**
     * 斜率优化, 发现有枚举行为时(即全部遍历),需要观察相邻的位置的值,看是否可以有依赖的
     * ?=a+b+c+d+........;
     * x=b+c+d+....
     * 推出 ? = x+a
     * @param array
     * @param aim
     * @return
     */
    public static int dp2(int[] array, int aim) {
        int N = array.length;
        int[][] dp = new int[N+1][aim + 1];
        dp[N][0]=1;
        //从下往上, 上面的依赖下面的
        for (int index = N-1; index >=0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                //优化版本。 相当于 ? = x+a
                dp[index][rest] = dp[index + 1][rest];
                if (rest - array[index] >= 0) {
                    dp[index][rest]+=dp[index][rest - array[index]];
                }
            }
        }
        return dp[0][aim];
    }
}
